package com.mc.string;
/**
 * Sunday 算法用于字符串匹配，和BM算法有些类似，需要一个辅助数组记录模式串中各个字符到最右端的距离
 * 匹配从左向右进行，当匹配失败时，根据匹配串后一个字符查询辅助数组确定偏移量
 * @author MC
 *
 */
public class Sunday {
	
	private int[] right = new int[256];
	private String pattern;
	public Sunday(String pattern){
		this.pattern = pattern;
		for(int i=0;i<right.length;i++){
			right[i] = pattern.length()+1;//初始化
		}
		for(int j=0;j<pattern.length();j++){
			right[pattern.charAt(j)]=pattern.length()-j;
		}
	}
	public int search(String text){
		int n = text.length();
		int m = pattern.length();
		int skip;
		for(int i=0;i<=n-m;i+=skip){
			skip=0;
			int temp_i = i;
			for(int j=0;j<m;j++){
				if(text.charAt(temp_i)!=pattern.charAt(j)){
					skip = right[text.charAt(i+m)];
					break;
				}
				temp_i++;
			}
			if(skip==0) return i;
		}
		return n;
	}
	
	public static void main(String[] args) {
		Sunday s = new Sunday("abc");
		System.out.println(s.search("cccabc"));
	}
}
